/* *
* 希尔排序是一种插入排序的改进，也称为缩小增量排序。它的基本思想是将待排序数组按照一定的步长进行分组，对每组进行插入排序，然后逐步缩小步长，继续进行排序，直到步长为1，完成排序
* 希尔排序的时间复杂度与步长序列有关，最坏情况下时间复杂度为O(n^2)。空间复杂度为O(1) 不稳定
* 希尔排序的流程如下：
* 1.选择一个步长序列，对数组按照该序列进行分组
* 2.对每组进行插入排序
* 3.缩小步长，重复步骤1和2，直到步长为1，完成排序
* */

function shellSort(arr) {

    let gap = 3
    while (gap > 0) {
        for (let i = gap; i < arr.length; i ++) {
            let j = i - gap
            let temp = arr[i]
            while (j >= 0 && temp < arr[j]) {
                arr[j + gap] = arr[j]
                j -= gap
            }
            arr[j + gap] = temp
        }
        console.log()
        gap = Math.floor(gap / 2)
    }
    return arr

}

const arr = [5,2,6,1,7,2,10,8]
console.log(shellSort(arr));
